package oj;

import java.util.ArrayList;
import java.util.List;

public class LC109 {
    //根据中序遍历的特点还原二叉树
    ListNode pre;
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null ) return null;
        if(head.next==null) return new TreeNode(head.val);

        pre=head;
        return buildTree(0,getLength(head)-1);
    }
    private TreeNode buildTree(int left,int right){
        if(left>right) return null;
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode();
        TreeNode leftNode=buildTree(left,mid-1);
        root.val=pre.val;
        pre=pre.next;
        root.left=leftNode;
        root.right=buildTree(mid+1,right);
        return root;
    }
    private int getLength(ListNode head){
        int len=0;
        while(head!=null){
            len++;
            head=head.next;
        }
        return len;
    }


    //快慢指针定位链表中点，进行建树
//    public TreeNode sortedListToBST(ListNode head) {
//        if(head==null ) return null;
//        if(head.next==null) return new TreeNode(head.val);
//        ListNode slow=head;
//        ListNode fast=head;
//        ListNode dummyHead=new ListNode(-1);
//        dummyHead.next=head;
//        ListNode node=dummyHead;
//        while(fast!=null && fast.next!=null){
//            node=node.next;
//            slow=slow.next;
//            fast=fast.next.next;
//        }
//        ListNode right=slow.next;
//        node.next=null;
//        TreeNode root=new TreeNode(slow.val);
//        root.left=sortedListToBST(head);
//        root.right=sortedListToBST(right);
//        return root;
//    }



//分治法，二分找中点
//    public TreeNode sortedListToBST(ListNode head) {
//        if(head==null ) return null;
//        if(head.next==null) return new TreeNode(head.val);
//        List<Integer> list =new ArrayList<>();
//        while(head!=null){
//            list.add(head.val);
//            head=head.next;
//        }
//        return buildTree(list,0,list.size()-1);
//    }
//    private TreeNode buildTree(List<Integer> list, int left,int right){
//        if(left>right) return null;
//        int mid=left+(right-left)/2;
//        TreeNode root=new TreeNode(list.get(mid));
//        root.left=buildTree(list,left,mid-1);
//        root.right=buildTree(list,mid+1,right);
//        return root;
//    }
}
